package com.Questions.bit_manipulation;

/**
 * 二进制求和
 * 将两个二进制字符串 求和并返回一个二进制字符串
 */
public class leetcode67 {
    // 先将ab都转化成十进制数 求和然后转化为 二进制数形成的字符串
    // 这种方法 基于java和python语言本身的高精度功能
//    public String addBinary(String a, String b) {
//        return Integer.toBinaryString(
//                Integer.parseInt(a, 2) + Integer.parseInt(b, 2)
//        );
//    }
    // 方法一 模拟列竖式的过程 逢二进一
    // 使用一个变量来存储 上一个位置的进位



//    public String addBinary(String a, String b) {
//        StringBuffer ans= new StringBuffer();
//        int n=Math.max(a.length(),b.length());
//        int carry=0;
//        for (int i = 0; i < n; ++i) {
//            carry += i < a.length() ? (a.charAt(a.length() - 1 - i) - '0') : 0;
//            carry += i < b.length() ? (b.charAt(b.length() - 1 - i) - '0') : 0;
//            ans.append((char) (carry % 2 + '0'));
//            carry /= 2;
//        }
//
//        return ans.toString();
//    }
public String addBinary(String a, String b) {
    int i = a.length() - 1;
    int j = b.length() - 1;
    int carry = 0;
    StringBuilder builder = new StringBuilder();
    //循环相加两个字符串相同长度的低位数部分
    while (i >= 0 && j >= 0) {
        int sum = carry;
        sum += a.charAt(i--) - '0';
        sum += b.charAt(j--) - '0';
        carry = sum / 2;
        builder.append(sum % 2);
    }
    // 如果 a 还没遍历完成（a串比b串长），则继续遍历添加 a 的剩余部分
    while (i >= 0) {
        int sum = carry + a.charAt(i--) - '0';
        carry = sum / 2;
        builder.append(sum % 2);
    }
    // 如果 b 还没遍历完成（b串比a串长），则继续遍历添加 b 的剩余部分
    while (j >= 0) {
        int sum = carry + b.charAt(j--) - '0';
        carry = sum / 2;
        builder.append(sum % 2);
    }
    //如果 carry 不等于0 还有个进位数没加进去，需要补充
    if (carry == 1) {
        builder.append(carry);
    }
    //反转字符串获得正常结果
    return builder.reverse().toString();
    }
}
